#include "stdafx.h"
#include "FollowWord.h"

namespace compile
{
	// ------------------------ Public --------------------

	FollowWord::FollowWord()
	{
	}

	FollowWord::FollowWord(Syntax* syntax, FirstWord* first)
		:FollowWord()
	{
		vector<Word>word_vector = (*syntax).getWordVector();
		map<string, set<string>>first_map = (*first).getFirst();
		string enter = (*syntax).getEnter();
		calculateFollow(&word_vector, &first_map, enter);
		word_vector.clear();
		first_map.clear();
	}

	FollowWord::~FollowWord()
	{
		follow.clear();
	}


	void FollowWord::printFollow() const
	{
		cout << endl << "Follow Set:" << endl;
		for (auto it = follow.begin(); it != follow.end(); ++it)
		{
			cout << it->first << '\t';
			for (auto is = it->second.begin(); is != it->second.end(); ++is)
			{
				cout << *is << ',';
			}
			cout << endl;
		}
	}

	map<string, set<string>> FollowWord::getFollow() const
	{
		return follow;
	}

	// ------------------------ End Public --------------------

	// ------------------------ Private -----------------------

	/**
	* calculate follow set
	* @param word_vector {vector<Word>*} - poniter of word set
	* @param first_map {map<string, set<string>>*} - pointer of first set
	* @param enter {string} - enter symbol
	*/
	void FollowWord::calculateFollow(vector<Word>* word_vector,
		map<string, set<string>>* first_map, string enter)
	{
		for (UNI i = 0; i < (*word_vector).size(); ++i)
		{
			string key = (*word_vector).at(i).getKey();
			set<string> fixed_set;
			// 访问检查
			set<string> insert_set = getSet(key,
				word_vector,
				first_map,
				enter, 
				&fixed_set);

			follow.insert(map<string, set<string>>
				::value_type(key, insert_set));
			insert_set.clear();
			fixed_set.clear();
		}

	}

	/**
	* 递归获取follow集合
	* @param key {string} - 句法的key
	* @param word_vector {vector<Word>*} - 文法集合
	* @param first_map {map<string, set<string>>* } - first集
	* @param enter {string} - 入口标记
	* @param fixed_set {set<string>*} - 标记该key是否已被访问
	* @return follow集
	*/
	set<string> FollowWord::getSet(string key,
		vector<Word>* word_vector,
		map<string, set<string>>* first_map,
		string enter,
		set<string>* fixed_set)
	{
		set<string> insert_set;

		// 如果是终结符直接返回，否则写入访问列表
		if (!ifEndSign(key[0]))
		{
			(*fixed_set).insert(key);
		}
		else
		{
			return insert_set;
		}

		// 如果是文法开始符号
		if (enter == key)
		{
			insert_set.insert("$");
		}

		UNI size = (*word_vector).size();

		// 迭代文法
		for (UNI i = 0; i < size; ++i)
		{
			string checked_key = (*word_vector).at(i).getKey();
			string checked_content = (*word_vector).at(i).getContent();
			int index = checkFollow(key, checked_content);
			if (index >= 0)
			{
				// 本行最后一个符号，checked_key加入
				if (index == checked_content.length() - 1)
				{
					if ((*fixed_set).find(checked_key) == (*fixed_set).end())
					{
						insert_set = concatSet(insert_set,
							getSet(checked_key, word_vector,
								first_map, enter, fixed_set));
					}
				}
				else
				{

					// first key
					string new_key = polyfillChar(checked_content[index + 1]);

					// 终结符
					if (ifEndSign(new_key[0]))
					{
						insert_set.insert(new_key);
					}
					else
					{
						// 获取其first集
						auto first_key_set = (*first_map).find(new_key);

						if (first_key_set != (*first_map).end())
						{
							if (first_key_set->second.find("$")
								!= first_key_set->second.end()
								&& (*fixed_set).find(new_key)
								== (*fixed_set).end())
							{
								insert_set = concatSet(insert_set,
									getSet(new_key, word_vector,
										first_map, enter, fixed_set));
							}

							insert_set = concatSet(insert_set,
								deleteEmptySign(first_key_set->second));

						}
					}
				}
			}
		}

		return insert_set;
	}


	/**
	* find key in content
	* @param key {string}
	* @param content {string}
	* @return i {int} - index of key
	*		  -1 cannot find key
	*/
	int FollowWord::checkFollow(string key, string content)
	{
		for (UNI i = 0; i < content.length(); ++i)
		{
			if (content[i] == key[0])
			{
				return i;
			}
		}
		return -1;
	}

	/**
	* whether the key can derive $
	* @param key {string} - checked syntax key
	* @param checked_set {set<string>*} - insert visited key to prevent stack overflow
	* @return true derive $
	*		  false cannot derive $
	*/
	bool FollowWord::checkEnd(string key, set<string>* checked_set) const
	{
		auto it = follow.find(key);
		string next_key;


		if (it != follow.end())
		{
			auto k = it->second.begin();

			if (!ifEndSign((*k)[0]) && (*k) != key)
			{
				next_key = (*k)[0];
			}

			for (auto i = k; i != it->second.end(); ++i)
			{
				for (unsigned int j = 0; j < (*i).length(); ++j)
				{
					if ((*i)[j] == '$')
					{
						return true;
					}
				}
			}
		}

		if ((*checked_set).find(next_key) != (*checked_set).end())
		{
			(*checked_set).insert(key);
			checkEnd(next_key, checked_set);
		}
		return false;
	}

	/**
	* check end sign
	* @param sign {char} - checked sign
	* @return true - End sign
	*		  false - not end sign
	*/
	bool FollowWord::ifEndSign(char sign)
	{
		if (!(sign >= 'A' && sign <= 'Z'))
		{
			return true;
		}
		return false;
	}

	/**
	* insert visited key to prevent stack overflow
	* @param if_visit {set<string>*} - note visited key
	* @param key {string} - checked key
	*/
	void FollowWord::checkVisited(set<string>* if_visit, string key)
	{
		if ((*if_visit).find(key) == (*if_visit).end())
		{
			(*if_visit).insert(key);
		}
	}

	/**
	* 检查是否为起始符号，如果是添加终结符
	* @param inset_set {set<string>*} - 要插入的Set
	* @param enter {string} - enter key
	* @param key {string} - checked key
	*/
	void FollowWord::checkEnter(set<string>* insert_set,
		string enter,
		string key)
	{
		if (key == enter)
		{
			(*insert_set).insert("$");
		}
	}

	/**
	* marge set
	* @param first_set {set<string>}
	* @param second_set {set<string>}
	* @return first_set {set<string>} - merged set
	*/
	set<string> FollowWord::concatSet(set<string> first_set,
		set<string> second_set)
	{
		for (auto it = second_set.begin(); it != second_set.end(); ++it)
		{
			first_set.insert((*it));
		}

		return first_set;
	}

	string FollowWord::polyfillChar(char new_char)
	{
		char a[2];
		a[0] = new_char;
		a[1] = '\0';

		return a;
	}

	/**
	* 删掉$ (用于将first集加入follow)
	* @param {set<string>} first_content - first集
	* @return {set<string>} - 处理完的first集
	*/
	set<string> FollowWord::deleteEmptySign(set<string>first_content)
	{
		auto it = first_content.find("$");
		if (it == first_content.end())
		{
			return first_content;
		}

		first_content.erase(it);

		return first_content;
	}

	// ------------------------ End Private -----------------------
}